{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canPermutePalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>&quot;code&quot;</code>\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>&quot;aab&quot;</code>\n",
    "<strong>输出:</strong> true</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>&quot;carerac&quot;</code>\n",
    "<strong>输出:</strong> true</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-permutation](https://leetcode.cn/problems/palindrome-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-permutation](https://leetcode.cn/problems/palindrome-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"code\"', '\"aab\"', '\"carerac\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            if c not in freq:\n",
    "                freq[c] = 1\n",
    "            else:\n",
    "                freq[c] += 1\n",
    "        num_odd = 0\n",
    "        for f in freq.values():\n",
    "            if f % 2 == 1:\n",
    "                num_odd += 1\n",
    "        return num_odd <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        res = 0\n",
    "        for i in set(s):\n",
    "            if s.count(i) % 2 != 0:\n",
    "                res += 1\n",
    "        if res > 1:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        from collections import Counter\n",
    "        cnt = 0\n",
    "        for k, v in Counter(s).items():\n",
    "            if v % 2:\n",
    "                cnt += 1\n",
    "        return cnt <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return len([k for k, v in Counter(s).items() if v % 2 != 0]) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        for v in dic.values():\n",
    "            if v % 2 == 1:\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        count_odd = 0\n",
    "        for i in dic:\n",
    "            if dic[i] % 2 == 1:\n",
    "                count_odd += 1\n",
    "            if count_odd > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 偶数的话全为偶数\n",
    "        # 奇数的话一个为奇数\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]] = 1\n",
    "            else:\n",
    "                dic[s[i]] += 1\n",
    "        count = 0\n",
    "        for k,v in dic.items():\n",
    "            if v%2 != 0:\n",
    "                count += 1\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for value in dic.values():\n",
    "            if value%2==1:\n",
    "                odd+=1\n",
    "                if odd>1:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        num = 0\n",
    "        for _, val in dic.items():\n",
    "            if val % 2 == 1:\n",
    "                num += 1\n",
    "            if num > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        c = Counter(s)\n",
    "        count = 0\n",
    "\n",
    "        for value in c.values():\n",
    "            \n",
    "            if value%2 != 0:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        #idea: for a string to be palindrome permutation, it must have the      following traits: 1. there can be at most one character which only appeared odd times. ex: abcba. note if there are two characters that only made odd appearance, then it is not palindrome. ex: abcbae 2. other than that single character, all other characters will have to make even times of appearance 3. thus we use a dictionary to store the characters with single appearance, if we iterate through the entire string and the odd dictionary's key is no more than 1, that means the above two conditions have been met, and we have a palindrome permutation. else, we should return false. \n",
    "\n",
    "        odd = {}\n",
    "        for cha in s:\n",
    "            if cha in odd.keys(): #check if character is in dictionary\n",
    "                del odd[cha] #if it is, then it has appeared even times now, del it from the dict\n",
    "            else:\n",
    "                odd[cha] = 0 #if it's not, then it has appeared odd times, add to the dict\n",
    "        if len(odd) <= 1: #after traversing through the str, it dict len is no more than 1, return true, else return false\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val %2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = {}\n",
    "        for char in s:\n",
    "            if char in d:\n",
    "                d[char] += 1\n",
    "            else:\n",
    "                d[char] = 1\n",
    "        ord_c = 1\n",
    "        for key, value in d.items():\n",
    "            #if value % 2 != 0:\n",
    "            if value & 1 != 0:\n",
    "                if ord_c == 0:\n",
    "                    return False\n",
    "                ord_c -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for c in s:\n",
    "            if c in dic:\n",
    "                dic[c] += 1\n",
    "            else:\n",
    "                dic[c] = 1\n",
    "        temp = {key:value for key,value in dic.items() if value %2 ==1}\n",
    "        print(temp)\n",
    "        if len(s) % 2 ==0:\n",
    "            if len(temp)>=1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            if len(temp) == 1:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic=defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val%2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        word_dict = {}\n",
    "        for char in s:\n",
    "            word_dict[char] = word_dict.get(char, 0) + 1\n",
    "        odd_count = 0\n",
    "        for value in word_dict.values():\n",
    "            if value % 2:\n",
    "                odd_count += 1\n",
    "            if odd_count > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        if not s:return True\n",
    "\n",
    "        list1 = []\n",
    "        for key in s:\n",
    "            if key not in list1:\n",
    "                list1.append(key)\n",
    "            else:\n",
    "                list1.remove(key)\n",
    "        return True if len(list1)<2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l1 = []\n",
    "        for i in s:\n",
    "            if i not in l1:\n",
    "                l1.append(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "                continue\n",
    "            if i in s and i in l1:\n",
    "                l1.remove(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "        return len(set(l1)) <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        h = defaultdict(int)\n",
    "        for char in s:\n",
    "            h[char] += 1\n",
    "\n",
    "        size = len(s)\n",
    "        odd_count = 0\n",
    "        for v in h.values():\n",
    "            if v % 2 != 0:\n",
    "                odd_count += 1\n",
    "\n",
    "        if odd_count > 1:\n",
    "            return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ans = []\n",
    "        for i in range(len(s)):\n",
    "            if s.count(s[i]) % 2 == 1:\n",
    "                if not ans and s[i] not in ans:\n",
    "                    ans.append(s[i])\n",
    "                elif ans and s[i] in ans:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        assist = []\n",
    "        for x in s:\n",
    "            if x in assist:\n",
    "                assist.remove(x)\n",
    "            else:\n",
    "                assist.append(x)\n",
    "        \n",
    "        return len(assist) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        hashmap = dict()\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            try:\n",
    "                hashmap[i] = not hashmap[i]\n",
    "                if hashmap[i]:\n",
    "                    res-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "            except:\n",
    "                hashmap[i] = False\n",
    "                res += 1\n",
    "        return res<2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = Counter(list(s))\n",
    "        a = 0\n",
    "        for k, v in c.items():\n",
    "            if v % 2:\n",
    "                a += 1\n",
    "            if a > 1:\n",
    "                return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        a=dict(Counter(s))\n",
    "        n,f=0,0\n",
    "    \n",
    "        for i in a.values():\n",
    "            if i%2==1:\n",
    "                f+=1\n",
    "            if f==2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canPermutePalindrome(self, s: str) -> bool:\n",
    "#         char_bitmap = [False] * 128\n",
    "#         for ch in s:\n",
    "#             pos = ord(ch)\n",
    "#             char_bitmap[pos] = not char_bitmap[pos]\n",
    "#         flag = False\n",
    "#         for i in range(128):\n",
    "#             if char_bitmap[i]:\n",
    "#                 if not flag:\n",
    "#                     flag = True\n",
    "#                 else:\n",
    "#                     return False\n",
    "#         return True\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = Counter(s)\n",
    "        t = 0\n",
    "        for key,val in dic.items():\n",
    "            if val % 2:\n",
    "                t += 1\n",
    "            if t > 1:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        one_chance = True\n",
    "        for v in cnt.values():\n",
    "            if v % 2 == 1 and one_chance:\n",
    "                one_chance = False\n",
    "            elif v % 2 == 1 and not one_chance:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        temp = set()\n",
    "        for i in s:\n",
    "            if i in temp:\n",
    "                temp.remove(i)\n",
    "            else:\n",
    "                temp.add(i)\n",
    "        if len(temp) == 0 or len(temp) == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# leetcode submit region begin(Prohibit modification and deletion)\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        char_bitmap = [False] * 128\n",
    "        for ch in s:\n",
    "            pos = ord(ch)\n",
    "            char_bitmap[pos] = not char_bitmap[pos]\n",
    "        flag = False\n",
    "        for i in range(128):\n",
    "            if char_bitmap[i]:\n",
    "                if not flag:\n",
    "                    flag = True\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "      carr = [0] * 122\n",
    "      isp = not (len(s)%2==0)\n",
    "      for car in s:\n",
    "        carr[ord(car)] += 1\n",
    "\n",
    "      for cad in carr:\n",
    "        if cad%2==0:\n",
    "          pass\n",
    "        elif isp:\n",
    "          isp = False\n",
    "        else:\n",
    "          return False\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = set()\n",
    "        for c in s:\n",
    "            if c in cnt:\n",
    "                cnt.remove(c)\n",
    "            else:\n",
    "                cnt.add(c)\n",
    "        return len(cnt) < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "                if error > 1:\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        record = set()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in record:\n",
    "                record.add(s[i])\n",
    "            else:\n",
    "                record.remove(s[i])\n",
    "        if (len(record) == 1 and len(s) %2 != 0) or (len(record) == 0 and len(s) %2 == 0):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l1 = []\n",
    "        for i in s:\n",
    "            if i not in l1:\n",
    "                l1.append(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "                continue\n",
    "            if i in s and i in l1:\n",
    "                l1.remove(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "        return len(set(l1)) <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l1 = []\n",
    "        for i in s:\n",
    "            if i not in l1:\n",
    "                l1.append(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "                continue\n",
    "            if i in s and i in  l1:\n",
    "                l1.remove(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "        return len(set(l1)) <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return sum(1 for v in Counter(s).values() if v%2) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        res = defaultdict(int)\n",
    "        for c in s:\n",
    "            res[c] += 1\n",
    "        count = 0\n",
    "        for v in res.values():\n",
    "            if v % 2 != 0:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return count == 0 if len(s) % 2 == 0 else count == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        lst = []\n",
    "        for i in s:\n",
    "            if i not in lst:\n",
    "                lst.append(i)\n",
    "            else:\n",
    "                lst.remove(i)\n",
    "        return len(lst) == 1 or len(lst)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ans=0\n",
    "        cnt=Counter(s)\n",
    "        for i in cnt:\n",
    "            ans+=cnt[i]%2\n",
    "        return ans<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        count = 0\n",
    "        for value in dic.values():\n",
    "            if value % 2:\n",
    "                count += 1\n",
    "        if count >=2:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        result = 0\n",
    "        for c in s:\n",
    "            result ^= 1 <<ord(c)\n",
    "            print(result)\n",
    "        return result & (result-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        s_count = {}\n",
    "        for char in s:\n",
    "            if char in s_count:\n",
    "                s_count[char] += 1\n",
    "            else:\n",
    "                s_count[char] = 1\n",
    "        \n",
    "        counts = 0\n",
    "        for s_key in s_count:\n",
    "            if s_count[s_key] % 2 == 1:\n",
    "                counts += 1\n",
    "        \n",
    "        if counts > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = Counter(s)\n",
    "        odd = 0\n",
    "        for v in c.values():\n",
    "            if v % 2 == 1:\n",
    "                odd += 1\n",
    "            if odd > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        odd = {}\n",
    "        \n",
    "        for ch in s:\n",
    "            if ch in odd.keys():\n",
    "                del odd[ch]\n",
    "            else:\n",
    "                odd[ch] = 0\n",
    "        if len(odd.keys()) > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        single_qty = 0\n",
    "        for v, k in dic.items():\n",
    "            if k % 2 == 1:\n",
    "                single_qty += 1\n",
    "                if single_qty > 1:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        l = [s.count(i) % 2 for i in set(s)]\n",
    "        if l.count(1) < 2:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "            if error > 1:\n",
    "                return False\n",
    "            \n",
    "        return (len(s) % 2 == 1 and error == 1) or (len(s) % 2 == 0 and error == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # s1=sorted(s)\n",
    "        l1=len(s)\n",
    "        s2=set(s)\n",
    "        count1=[]\n",
    "        count2=0\n",
    "        \n",
    "        for i in s2:\n",
    "            count1.append(s.count(i))\n",
    "        if l1%2==0:\n",
    "            for j in range(len(count1)):\n",
    "                if count1[j]%2!=0:\n",
    "                    return False\n",
    "                return True\n",
    "        else:\n",
    "            for j in range(len(count1)):\n",
    "                if count1[j]%2!=0:\n",
    "                    count2=count2+1\n",
    "            if count2>1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 判断回文双指针,但是这道题本身指的是str的排列,不是str本身\n",
    "        # 所以从满足回文串的充要条件上出发, 如果是回文的.str长度\n",
    "        # 偶数的话, 所有字符出现的次数一定是偶数次\n",
    "        # 奇数的话, 所有字符出现的次数一定是偶数次, 加一个字符是奇数次\n",
    "        # hash\n",
    "        \n",
    "        # cac >>  caac  aab\n",
    "        s_dict = Counter(s)\n",
    "        odd_num = 0 # 初始化，记录频率次数是奇数的字符个数, 只记录这个就行了, 剩下的一定是偶数\n",
    "        for i,val in s_dict.items(): \n",
    "            if val%2!=0:\n",
    "                odd_num+=1\n",
    "            if odd_num > 1:  # 优化: 只要频率次是奇数的字符个数大于1,肯定F\n",
    "                return False\n",
    "        return True\n",
    "        # ou_num = len(s)-odd_num\n",
    "\n",
    "        # if len(s)%2==0: # str长度为偶数\n",
    "        #     if odd_num!=0:\n",
    "        #         return False\n",
    "        #     else:\n",
    "        #         return True\n",
    "        # else: # 奇数\n",
    "        #     if odd_num ==1:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # if len(s)<= 2:\n",
    "        #     return True\n",
    "        a = Counter(s)\n",
    "        c =[]\n",
    "        for i in a.keys():\n",
    "            if a.get(i) %2 !=0:\n",
    "                c.append(i)\n",
    "        if len(c)>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        di = defaultdict(int)\n",
    "        for c in s:\n",
    "            if di[c] == 0:\n",
    "                di[c] += 1\n",
    "            else:\n",
    "                di[c] -= 1\n",
    "        count = 0\n",
    "        for n in di:\n",
    "            if di[n] != 0:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        m = {}\n",
    "        for c in s:\n",
    "            m[c] = m.get(c,0) + 1\n",
    "        odd_count = 0\n",
    "        for c in m:\n",
    "            if m[c] % 2:\n",
    "                odd_count += 1\n",
    "        return odd_count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(bool)\n",
    "        for c in s:\n",
    "            dic[c] = not dic[c]\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val is True:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "            if error > 1:\n",
    "                return False\n",
    "            \n",
    "        return (len(s) % 2 == 1 and error == 1) or (len(s) % 2 == 0 and error == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\"tactcoa\"\n",
    "\"code\"\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        # no more than one odd\n",
    "        odds = 0\n",
    "        for v in cnt.values():\n",
    "            if v % 2 != 0:\n",
    "                odds += 1\n",
    "            if odds > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        rs=0\n",
    "        for c in s:\n",
    "            rs ^= 1 << ord(c)\n",
    "        return rs & (rs-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        count = Counter(s)\n",
    "        ans = 0\n",
    "        for key, value in count.items():\n",
    "            if value%2 == 1:\n",
    "                ans += 1\n",
    "        return ans<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        \n",
    "        odd = 0\n",
    "        for value in dic.values():\n",
    "            if value % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        s=collections.Counter(s)\n",
    "        return sum(i%2!=0 for i in s.values())<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        tmp = {}\n",
    "        for c in s:\n",
    "            if c not in tmp:\n",
    "                tmp[c] = 1\n",
    "            else:\n",
    "                tmp[c] += 1\n",
    "        count = 0\n",
    "        for k in tmp:\n",
    "            if tmp[k] % 2 == 1:\n",
    "                count += 1\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(bool)\n",
    "        for c in s:\n",
    "            d[c] = not d[c]\n",
    "        flag = False\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                flag = not flag\n",
    "                if flag is False:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "                if error > 1:\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(bool)\n",
    "        for c in s:\n",
    "            d[c] = not d[c]\n",
    "        flag = False\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                if flag:\n",
    "                    return False\n",
    "                flag = not flag\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        dic = defaultdict(int)\n",
    "        for char in s:\n",
    "            dic[char] += 1\n",
    "        \n",
    "        odd_num = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd_num += 1\n",
    "                if odd_num == 2:\n",
    "                   return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        flag = False\n",
    "        for ch in cnt:\n",
    "            if cnt[ch] & 1:\n",
    "                if flag:\n",
    "                    return False\n",
    "                flag = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(bool)\n",
    "        for c in s:\n",
    "            d[c] = not d[c]\n",
    "        flag = False\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                if flag:\n",
    "                    return False\n",
    "                flag = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        arr = []\n",
    "        for ch in s:\n",
    "            if ch not in arr:\n",
    "                arr.append(ch)\n",
    "            else:\n",
    "                arr.pop(arr.index(ch))\n",
    "        return True if len(arr) <= 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ret = 0\n",
    "        for c, n in Counter(s).items():\n",
    "            ret += n % 2\n",
    "        if ret > 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val%2 == 1:\n",
    "                odd+= 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        count: Dict[str, int] = Counter(s)\n",
    "        odd_count: int = sum(c % 2 for c in count.values())\n",
    "\n",
    "        return (\n",
    "            (len(s) % 2 == 0 and odd_count == 0)\n",
    "            or\n",
    "            (len(s) % 2 == 1 and odd_count == 1)\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return sum(val % 2 == 1 for key,val in Counter(s).items()) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        storage = {}\n",
    "\n",
    "        for char in s:\n",
    "            if char not in storage:\n",
    "                storage[char] = 1\n",
    "            else:\n",
    "                storage[char] += 1\n",
    "\n",
    "        odd = 0\n",
    "\n",
    "        for value in list(storage.values()):\n",
    "            if value % 2 == 1:\n",
    "                odd += 1\n",
    "            if odd > 1:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 初始化哈希表\n",
    "        dic = defaultdict(int)\n",
    "        # 统计字符串中各字符的数量\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            # 统计“数量为奇数”字符的个数\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                # 若“数量为奇数”的字符个数 > 1 ，则不是回文串排列\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        # 若“数量为奇数”的字符个数 <= 1 ，则是回文串排列\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        mp = {}\n",
    "        for k in s:\n",
    "            mp[k] = mp.get(k, 0) + 1\n",
    "        odd, even = 0, 0\n",
    "        for k, v in mp.items():\n",
    "            if v % 2 == 1:\n",
    "                odd += 1\n",
    "            else:\n",
    "                even += 1\n",
    "        re = odd <= 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        hashmap = {}\n",
    "        for i in s:\n",
    "            if i in hashmap:\n",
    "                hashmap[i]+=1\n",
    "            else:\n",
    "                hashmap[i]=1\n",
    "        flag = False\n",
    "        for item in hashmap:\n",
    "            if hashmap[item]%2==0:\n",
    "                pass\n",
    "            elif not flag and hashmap[item]%2==1:\n",
    "                flag = True\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        if len(s) == 1:\n",
    "            return True\n",
    "\n",
    "        freq = {}\n",
    "        for s_ in s:\n",
    "            if s_ in freq:\n",
    "                freq[s_] += 1\n",
    "            else:\n",
    "                freq[s_] = 1\n",
    "        odd = 0\n",
    "        for k, v in freq.items():\n",
    "            if v%2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for c in s:\n",
    "            dic[c] = dic.get(c,0) + 1 \n",
    "        count = 0 \n",
    "        for v in dic.values():\n",
    "            if v%2 == 1:\n",
    "                count += 1 \n",
    "        return count < 2 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 ==1:\n",
    "                odd+=1\n",
    "                if odd >1: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        from collections import Counter\n",
    "        dict_counts = Counter(s)\n",
    "        k = 0\n",
    "        for v in dict_counts.values():\n",
    "            if v % 2 != 0:\n",
    "                k += 1\n",
    "        return k <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        \"\"\"\n",
    "        >>> canPermutePalindrome(\"code\")\n",
    "        False\n",
    "        >>> canPermutePalindrome(\"aab\")\n",
    "        True\n",
    "        >>> canPermutePalindrome(\"carerac\")\n",
    "        True\n",
    "        \"\"\"\n",
    "        counter = Counter()\n",
    "        for c in s:\n",
    "            counter[c] += 1\n",
    "        single_count = 0\n",
    "        for c in counter:\n",
    "            if counter[c] % 2 == 1:\n",
    "                if single_count > 0:\n",
    "                    return False\n",
    "                single_count += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        a = set()\n",
    "        for chr in s:\n",
    "            if chr in a:\n",
    "                a.remove(chr)\n",
    "            else:\n",
    "                a.add(chr)\n",
    "        \n",
    "        return len(list(a)) < 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = collections.Counter(s)\n",
    "        n = len(s)\n",
    "\n",
    "        n_odd = 0\n",
    "\n",
    "        for _, val in cnt.items():\n",
    "            if val % 2:\n",
    "                n_odd += 1\n",
    "                if n_odd > 1:\n",
    "                    return False\n",
    "\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        num = 0\n",
    "        for item in s:\n",
    "            if item not in dic:\n",
    "                dic[item] = 1\n",
    "            else: dic[item] +=1\n",
    "        for key,value in dic.items():\n",
    "            if value%2 ==1:\n",
    "                num +=1\n",
    "        if num >1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 初始化哈希表\n",
    "        dic = defaultdict(int)\n",
    "\n",
    "        # 统计字符串中各字符的数量\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        \n",
    "        odd = 0\n",
    "\n",
    "        for val in dic.values():\n",
    "            # 统计“数量为奇数”字符的个数\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                # 若“数量为奇数”的字符个数 > 1，则不是回文串排列\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        \n",
    "        # 若“数量为奇数”的字符个数 <= 1，则是回文串排列\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l = len(s)\n",
    "        hashmap = {}\n",
    "        countodd = 0\n",
    "        for i in s:\n",
    "            if i not in hashmap:\n",
    "                hashmap[i] = 1\n",
    "            else:\n",
    "                hashmap[i] += 1\n",
    "            \n",
    "        if l % 2 == 0:\n",
    "            for i in hashmap.values():\n",
    "                if i % 2 != 0:\n",
    "                    return False\n",
    "                    break\n",
    "        else:\n",
    "            for i in hashmap.values():\n",
    "                if i % 2 != 0:\n",
    "                    countodd += 1\n",
    "                    if countodd > 1:\n",
    "                        return False\n",
    "                        break\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        hashmap = {}\n",
    "\n",
    "        for i in s:\n",
    "            if i not in hashmap:\n",
    "                hashmap[i] = 1\n",
    "            else:\n",
    "                hashmap[i] += 1\n",
    "\n",
    "        count = 0\n",
    "        for i in hashmap.values():\n",
    "            if i % 2 != 0:\n",
    "                count += 1\n",
    "\n",
    "        if count > 1 :\n",
    "            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        count = collections.Counter(s)\n",
    "        odd = 0\n",
    "        for chac in count:\n",
    "            if count[chac] % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd >= 2:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        char_set = set()\n",
    "        for char in s:\n",
    "            if char in char_set:\n",
    "                char_set.remove(char)\n",
    "            else:\n",
    "                char_set.add(char)\n",
    "        return len(char_set) <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        #让你判断字典里的数\n",
    "        dict={}\n",
    "        i=0\n",
    "        for item in s:\n",
    "            if item in dict:\n",
    "                dict[item]+=1\n",
    "            else:\n",
    "                dict[item]=1\n",
    "        #将所有的字母放入字符串中，如果出现val值大于1以上的情况，判别false\n",
    "        for key in dict:\n",
    "            if dict[key] %2 ==1:\n",
    "                i+=1\n",
    "        if i>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        if not s: return True\n",
    "\n",
    "        counter = Counter(s)\n",
    "        res = 0\n",
    "        odd_num = 0\n",
    "\n",
    "        for char, freq in counter.items():\n",
    "            if freq % 2 != 0:\n",
    "                odd_num += 1\n",
    "            if odd_num >= 2:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        s=Counter(s)\n",
    "        cnt=0\n",
    "        for key,val in s.items():\n",
    "            if val%2==1:\n",
    "                if cnt==0:\n",
    "                    cnt=1\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "      evennum = 0\n",
    "      even = []\n",
    "      res = True\n",
    "      for i in s:\n",
    "        if s.count(i) % 2 == 1 and i not in even: \n",
    "          evennum += 1\n",
    "          even.append(i)\n",
    "        if evennum > 1:res = False\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        count = 0\n",
    "        carry =[]\n",
    "        for i in s:\n",
    "            if i not in carry and s.count(i)%2 == 1:\n",
    "                carry.append(i)                \n",
    "                count +=1\n",
    "        if count > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        flag = 0\n",
    "        my_dict = Counter(s)\n",
    "\n",
    "        for key in my_dict:\n",
    "            if my_dict[key] % 2 == 0:\n",
    "                continue\n",
    "            else:\n",
    "                flag += 1\n",
    "        return flag <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        #有多个字母有两个/四个 只有一个字母有一个\n",
    "        dic = defaultdict(int)\n",
    "        count = 0\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        for val in dic.values():\n",
    "            if val %2 == 0:\n",
    "                pass\n",
    "            if val % 2 == 1:\n",
    "                count = count+1\n",
    "                if count == 2:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = collections.Counter(s)\n",
    "\n",
    "        odd = 0\n",
    "        for v in c.values():\n",
    "            odd += v % 2\n",
    "        return odd < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = collections.Counter(s)\n",
    "\n",
    "        odd = 0\n",
    "        for v in c.values():\n",
    "            odd += v % 2\n",
    "        return odd < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt=Counter(s)\n",
    "        ans=0\n",
    "        for key,value in cnt.items():\n",
    "            if value %2==1:\n",
    "                ans+=1\n",
    "                if ans!=1:\n",
    "                    return False\n",
    "        return True\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        seen = set()\n",
    "        for char in s:\n",
    "            if char in seen:\n",
    "                seen.remove(char)\n",
    "            else:\n",
    "                seen.add(char)\n",
    "        return len(seen) < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 最多只允许有一个单数的字母，除此之外其余的都是偶数个\n",
    "        hashmap = set()\n",
    "        for ch in s:\n",
    "            if ch not in hashmap:\n",
    "                hashmap.add(ch)\n",
    "            else:\n",
    "                hashmap.remove(ch)\n",
    "        if len(hashmap) <= 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        k = collections.Counter(s)\n",
    "        odd = 0\n",
    "        for k, v in k.items():\n",
    "            if v % 2 == 1:\n",
    "                odd += 1\n",
    "        return odd <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        t=Counter(s)\n",
    "        count=0\n",
    "        for v in t.values():\n",
    "            if v%2==1:\n",
    "                count+=1\n",
    "            if count>1:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        counter = collections.Counter(s)\n",
    "        countOfOdd = 0\n",
    "        for char, count in counter.items():\n",
    "            if count % 2:\n",
    "                countOfOdd += 1\n",
    "            if countOfOdd > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        m = {}\n",
    "        for i in s:\n",
    "            if i in m:\n",
    "                m[i] += 1\n",
    "            else:\n",
    "                m[i] = 1\n",
    "        count = 0\n",
    "        for k, v in m.items():\n",
    "            if v % 2 == 1:\n",
    "                count += 1\n",
    "        if count > 1:\n",
    "            return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        #让你判断字典里的数\n",
    "        dict={}\n",
    "        i=0\n",
    "        for item in s:\n",
    "            if item in dict:\n",
    "                dict[item]+=1\n",
    "            else:\n",
    "                dict[item]=1\n",
    "        #将所有的字母放入字符串中，如果出现val值大于1以上的情况，判别false\n",
    "        for key in dict:\n",
    "            if dict[key] %2 ==1:\n",
    "                i+=1\n",
    "        if i>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        import collections\n",
    "        map = collections.Counter(s)\n",
    "        count = 0\n",
    "        for k, v in map.items():\n",
    "            if v % 2 == 1:\n",
    "                count += 1\n",
    "                if count >= 2:\n",
    "                    return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        if len(s) % 2 == 1:\n",
    "            flag = False\n",
    "            for c in cnt:\n",
    "                if cnt[c] % 2 == 1 :\n",
    "                    if not flag:\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "            return True\n",
    "        else:\n",
    "            flag = False\n",
    "            for c in cnt:\n",
    "                if cnt[c] % 2 == 1 :\n",
    "                    if not flag:\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            if cnt.get(char) is not None:\n",
    "                cnt.pop(char)\n",
    "            else:\n",
    "                cnt[char] = 0\n",
    "        return len(cnt.values()) < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        count = collections.Counter(s)\n",
    "        ans = 0\n",
    "        for k,v in count.items():\n",
    "            if v%2 != 0:\n",
    "                ans += 1\n",
    "        if ans>1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic1={}\n",
    "        num=0\n",
    "\n",
    "        for char in s:\n",
    "            dic1[char]=dic1.get(char,0)+1\n",
    "\n",
    "        for char,count in dic1.items():\n",
    "            if count%2==0: continue\n",
    "            else: \n",
    "                num+=1\n",
    "                if num>1: return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = Counter(s)\n",
    "        odd = 0\n",
    "        for v in c.values():\n",
    "            if v % 2 != 0:\n",
    "                odd += 1\n",
    "        if odd>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        res = [c for c in cnt.values() if c % 2 != 0]\n",
    "        return len(res) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(int)\n",
    "        for c in s:\n",
    "            d[c] = 1-d[c]\n",
    "        cnt = 0\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                cnt += 1\n",
    "            if cnt > 1:\n",
    "                return False\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic1={}\n",
    "        num=0\n",
    "\n",
    "        for char in s:\n",
    "            dic1[char]=dic1.get(char,0)+1\n",
    "\n",
    "        for char,count in dic1.items():\n",
    "            if count%2==0: continue\n",
    "            else: \n",
    "                num+=1\n",
    "                if num>1: return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return sum(val % 2 == 1 for key,val in Counter(s).items()) <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canPermutePalindrome(self, s: str) -> bool:\n",
    "#         dic=Counter(s)\n",
    "#         count=0\n",
    "#         for c in dic.values():\n",
    "#             if c%2!=0:\n",
    "#                 count+=1\n",
    "#         if count>1:\n",
    "#             return False\n",
    "#         else:\n",
    "#             return True\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic=Counter(s)\n",
    "        count=0\n",
    "\n",
    "        for key,value in dic.items():\n",
    "            if value%2!=0:\n",
    "                count+=1\n",
    "        if count>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        char_cnt_dict: Dict[str, int] = dict()\n",
    "        for char in s:\n",
    "            if char in char_cnt_dict:\n",
    "                char_cnt_dict[char] = char_cnt_dict[char] + 1\n",
    "            else:\n",
    "                char_cnt_dict[char] = 1\n",
    "            \n",
    "        odd_cnt_num = 0\n",
    "        for char in char_cnt_dict.keys():\n",
    "            cnt = char_cnt_dict[char]\n",
    "            if cnt % 2 != 0:\n",
    "                odd_cnt_num = odd_cnt_num + 1\n",
    "            \n",
    "        return odd_cnt_num in (0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic=Counter(s)\n",
    "        count=0\n",
    "        for c in dic.values():\n",
    "            if c%2!=0:\n",
    "                count+=1\n",
    "        if count>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = collections.Counter(s)\n",
    "        n = len(s)\n",
    "\n",
    "        n_odd = 0\n",
    "\n",
    "        for _, val in cnt.items():\n",
    "            if val % 2:\n",
    "                n_odd += 1\n",
    "\n",
    "        return (n_odd == 1 and n % 2 == 1) or (n_odd == 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = collections.Counter(s)\n",
    "\n",
    "        n = len([x for x in dic.values() if x%2==1])\n",
    "        return n <= 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        odds = 0\n",
    "        overlap = []\n",
    "        for i in s:\n",
    "            if i not in overlap:\n",
    "                count_i = s.count(i)\n",
    "                if count_i%2 == 1:\n",
    "                    odds += 1\n",
    "                overlap.append(i)\n",
    "        if odds > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)#初始化哈希表\n",
    "        for c in s:#遍历字符串\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():#遍历哈希表，val为频次\n",
    "            if val % 2 == 1:#是否为奇数，如果是奇数，则odd加1\n",
    "                odd += 1#奇数个数\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        from collections import Counter\n",
    "        dict = Counter(s)\n",
    "        count = 0\n",
    "        for k, v in dict.items():\n",
    "            if v % 2 == 1:\n",
    "                count += 1\n",
    "        \n",
    "        if count > 1:\n",
    "            return False\n",
    "            \n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        a_dict = {}\n",
    "        for i in s:\n",
    "            if i not in a_dict:\n",
    "                a_dict[i] = 1\n",
    "            else:\n",
    "                a_dict[i] += 1\n",
    "        ct = 0\n",
    "        for i in a_dict:\n",
    "            if a_dict[i] % 2 != 0:\n",
    "                ct += 1\n",
    "        if ct > 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        bucket = {}\n",
    "        for i in s:\n",
    "            if i in bucket:\n",
    "                bucket[i] += 1\n",
    "            else:\n",
    "                bucket[i] = 1\n",
    "        \n",
    "        odd_nums = 0\n",
    "        for i in bucket:\n",
    "            if bucket[i] % 2 != 0:\n",
    "                odd_nums += 1\n",
    "        return False if odd_nums > 1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 哈希 + 抵消计数法（对称思想）！\n",
    "        char2num = defaultdict(int)\n",
    "        for c in s:\n",
    "            char2num[c] = 0 if char2num[c] else 1 # 存在的就抵消掉\n",
    "            if char2num[c] == 0: del char2num[c]\n",
    "\n",
    "        return not char2num or len(char2num) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dict_set =set()\n",
    "        for ch in s:\n",
    "            if ch in dict_set:\n",
    "                dict_set.remove(ch)\n",
    "            else:\n",
    "                dict_set.add(ch)\n",
    "        \n",
    "        if len(dict_set) == 1 or len(dict_set) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return sum(v & 1 for v in Counter(s).values()) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        from collections import Counter\n",
    "        dict_counts = Counter(s)\n",
    "        k = 0\n",
    "        for v in dict_counts.values():\n",
    "            if v % 2 != 0:\n",
    "                k += 1\n",
    "        return k <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        odd_once = False\n",
    "        for char, count in collections.Counter(s).items():\n",
    "            if count % 2 == 0:\n",
    "                continue\n",
    "            if odd_once:\n",
    "                return False\n",
    "            odd_once = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for w in s:\n",
    "            dic[w] += 1\n",
    "        odd = 0\n",
    "        for value in dic.values():\n",
    "            if value % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = {}\n",
    "        odd = 0\n",
    "        for num in s:\n",
    "            if num in d:\n",
    "                d[num]+=1\n",
    "            else:\n",
    "                d[num] = 1\n",
    "\n",
    "        for key in d.keys():\n",
    "            if d[key]%2==1:\n",
    "                odd+=1\n",
    "                if odd >1:\n",
    "                    return False\n",
    "        \n",
    "        return True\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        res_dict = {}\n",
    "        for i in s:\n",
    "            if i not in res_dict.keys():\n",
    "                res_dict[i] = 1\n",
    "            else:\n",
    "                res_dict[i] += 1\n",
    "        count = 0\n",
    "        for v in res_dict.values():\n",
    "            if v % 2 == 1:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        if count <= 1:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i,0)+1\n",
    "        count = 0\n",
    "        for i in dic.values():\n",
    "            if i%2==1:\n",
    "                count+=1\n",
    "        return count<2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for i in s:\n",
    "            dic[i]+=1\n",
    "        count=0\n",
    "        for i,j in dic.items():\n",
    "            if j%2!=0:\n",
    "                count+=1\n",
    "                if count==2:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        maps = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            maps[c] += 1\n",
    "        flag = 0\n",
    "        for v in maps.values():\n",
    "            if v % 2 == 1:\n",
    "                flag+=1\n",
    "                if flag > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\r\n",
    "        dic = {}\r\n",
    "        for i in s:\r\n",
    "            dic[i] = dic.get(i,0)+1\r\n",
    "        count = 0\r\n",
    "        for i in dic.values():\r\n",
    "            if i%2==1:\r\n",
    "                count+=1\r\n",
    "        return count<2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ### 最多有且只有一个字符出现的次数为奇数个，其他字符出现的次数全部为偶数个\n",
    "\n",
    "        char_freq = {}\n",
    "        for c in s:\n",
    "            if c not in char_freq:\n",
    "                char_freq[c]=1\n",
    "            else: \n",
    "                char_freq[c] += 1\n",
    "        cnt = 0\n",
    "        for value in char_freq.values():\n",
    "            if value % 2==1:\n",
    "                cnt+=1\n",
    "        if cnt>1: return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dt=dict()\n",
    "        for i in s:\n",
    "            if i in dt:\n",
    "                dt[i]+=1\n",
    "            else:\n",
    "                dt[i]=1\n",
    "        c=0\n",
    "        for key in dt.keys():\n",
    "            if dt[key]%2==1:\n",
    "                c+=1\n",
    "        return c<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic=defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd +=1\n",
    "                if odd >1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @cache\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        odd=0\n",
    "        for ch in s:\n",
    "            dic[ch]+=1\n",
    "        for val in dic.values():\n",
    "            if val%2==1:\n",
    "                odd+=1\n",
    "                if odd>1:\n",
    "                    return False\n",
    "        return True\n",
    "    #     self.res = []\n",
    "    #     n = len(s)\n",
    "    #     self.backtrack(s,\"\",n)\n",
    "    #     for i in self.res:\n",
    "    #         if i ==True :\n",
    "    #             return True\n",
    "    #     return False\n",
    "    # @cache\n",
    "    # def backtrack(self,temp,result,n):\n",
    "    #     if len(result)==n:\n",
    "    #         # print(result)\n",
    "    #         if result[::-1]==result:\n",
    "    #             self.res.append(True)\n",
    "    #         # else:\n",
    "    #         #     return None\n",
    "    #     for i in range(len(temp)):\n",
    "    #         # print(result+temp[i])\n",
    "    #         self.backtrack(temp[:i]+temp[i+1:],result+temp[i],n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        s = collections.Counter(s)\n",
    "        num = 0\n",
    "        for i in s:\n",
    "            if s[i] % 2 != 0:\n",
    "                num += 1\n",
    "                if num == 2:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        a_dict = {}\n",
    "        for i in s:\n",
    "            if i not in a_dict:\n",
    "                a_dict[i] = 1\n",
    "            else:\n",
    "                a_dict[i] += 1\n",
    "        ct = 0\n",
    "        for i in a_dict:\n",
    "            if a_dict[i] % 2 != 0:\n",
    "                ct += 1\n",
    "        if ct > 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        look_up = {}\n",
    "        for i in s:\n",
    "            if i not in look_up:\n",
    "                look_up[i] = 1\n",
    "            else:\n",
    "                look_up[i] += 1\n",
    "        \n",
    "        cnt = 0\n",
    "        for v in look_up.values():\n",
    "            if v % 2 == 1:\n",
    "                cnt += 1\n",
    "        \n",
    "        if cnt > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
